package com.leecode;

import java.util.ArrayList;
import java.util.List;

public class Leet22 {
	public static void main(String[] args) {
//		new Leet22().generateParenthesis(1);
//		new Leet22().generateParenthesis(2);
//		new Leet22().generateParenthesis(3);
		new Leet22().generateParenthesis2(3);
	}

	public List<String> generateParenthesis(int n) {
		if(n==0)return null;
		List<String> res=new ArrayList();
		dfs("",n,n,res);
		return res;
	}
	//left和right代表剩余多少次数
	public void dfs(String s,int left,int right,List<String> res) {
		if (left == 0 && right == 0) {//end
			res.add(s);
			return;
		}
		if (left > right) {
			return;
		} else {
			if (left > 0) {
				dfs(s + "(", left - 1, right, res);
			}
			if (right > 0) {
				dfs(s+")",left,right-1,res);
			}
			/**
			 * 如果你能画出
			 *              "" 2 2
			 *      ( 1 2           ) 2 1
			 * (( 0 2   () 1 1
			 * 就会清楚知道自减导致从"" 2 2 ->dfs-> ( 1 2的时候,因为left的自减变为了"" 1 2,暂时不管后续,这里就已经出现bug了
			 */
//			if(left>0)dfs(s+"(",--left,right,res);
//			if(right>0)dfs(s+")",left,--right,res);
		}
	}


	public List<String> generateParenthesis2(int n) {
		List<String> res = new ArrayList();
		if (n == 0) return res;

		StringBuilder sb = new StringBuilder("");
		backTrace(res, sb, n, 0, 0);
		return res;
	}

	/**
	 * 考点:如何写出特定的优雅的选择列表!!在熟悉backTrace后,第二次书写错了"选择列表"!!!(后来debug才发现是审题错了,我写的是全排列,题要的是合适括号组合)
	 * bug:++写习惯了容易在这题出bug!!!
	 * 心得:第二次看上面,看出了1.结束;2.优雅剪枝;3.代码少
	 * 心得2:剪枝的条件是根据结束"引导得出的",如上面是"强调剩余",所以剪枝也用"剩余"来判断,下面是我"仿别人的优雅代码"写出的4步backTrace
	 * bug2:4.一定要紧跟backTrace,不能把这行提出来放到最后(会出bug).
	 */
	public void backTrace(List<String> res, StringBuilder sb, int n, int left, int righ) {
		if (left + righ == 2 * n) {//1.结束
			res.add(sb.toString());
			return;
		}
		if (left < righ) return;//2.剪枝

		if (left < n) {//3.recur
			backTrace(res, sb.append("("), n, left + 1, righ);
			sb.deleteCharAt(sb.length() - 1);//4.一定要紧跟backTrace,不能把这行提出来放到最后(会出bug).
		}
		if (righ < n) {
			backTrace(res, sb.append(")"), n, left, righ + 1);
			sb.deleteCharAt(sb.length() - 1);
		}


		// for(int a=0;a<2;a++){
		//     if(left==3){
		//         sb.append(")");
		//         righ++;
		//     }else if(righ==3){
		//         sb.append("(");
		//         left++;
		//     }else{
		//         if(a==0){
		//             sb.append("(");
		//             left++;
		//         }else{
		//             sb.append(")");
		//             righ++;
		//         }
		//     }

		//     backTrace(res,sb,n,left,righ);
		//     sb.deleteCharAt(sb.length()-1);
		// }

//		if(left<3 && righ<3){
//			for(int a=0;a<2;a++){
//				if(a==0){
//					sb.append("(");
//					backTrace(res,sb,n,left+1,righ);
//					sb.deleteCharAt(sb.length()-1);
//				}else{
//					sb.append(")");
//					backTrace(res,sb,n,left,righ+1);
//					sb.deleteCharAt(sb.length()-1);
//				}
//			}
//		}else if(left==3 && righ<3){
//			sb.append(")");
//			backTrace(res,sb,n,left,righ+1);
//			sb.deleteCharAt(sb.length()-1);
//		}else if(left<3 && righ==3){
//			sb.append("(");
//			backTrace(res,sb,n,left+1,righ);
//			sb.deleteCharAt(sb.length()-1);
//		}

	}

}
